import java.util.Arrays;

/*
*  希尔排序
* */
public class shellSort {
    public static void sort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
        shell(arr, 1);
    }

    private static void shell(int[] arr, int gap) {
        for (int i = 1; i < arr.length; i++) { // 控制整个数组的循环
            int temp = arr[i]; // 假定 数组的第一位是有序的，所以把数组的第二位用来比较
            int j;
            for ( j = i-gap; j >= 0 ; j -= gap) { // 把 i 下标 之前的数进行排序
                if (arr[j] > temp) { // 如果 要比较的数 大于 前一位，就把前一位的数值进行交换
                    arr[j+gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+gap] = temp; // j 下标已经到了 -1 的位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {7,5,6,4,3,1,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
